// 688. “马”在棋盘上的概率

//* 暴力递归搜索，=>可以优化成记忆话搜索
function knightProbability_(N: number, K: number, r: number, c: number): number {
    return K==0? (inBoard(N,r,c)? 1:0) : search(N,K,r,c)
};

const addX = [-2,-2,-1,-1,1,1,2,2]
const addY = [-1,1,-2,2,-2,2,-1,1]


function inBoard(N:number,x:number,y:number):boolean{
    return x>=0&&x<N&&y>=0&&y<N
}

function search(N: number, K: number, r: number, c: number):number{
    let ans = 0
    for(let i=0;i<addX.length;i++){
        const newX = r + addX[i]
        const newY = c + addY[i]
        if(inBoard(N,newX,newY)){
            if(K==1) ans+=0.125
            else ans+=0.125*search(N,K-1,newX,newY)
        }
    }
    return ans
}

//* dp
function knightProbability(N: number, K: number, r: number, c: number): number {
    // n*n*k+1的三位数组
    const dp = new Array(N).fill(0).map(e=>new Array(N).fill(0).map(e=>new Array(K+1).fill(0)))  
    //! 一直没想到这种上下左右各个方向的图的题也可以用dp，原来的dp一般都是左上到右下，直接ij循环就行，就是单纯地加一个状态
    dp[r][c][0] = 1
    for(let k=1;k<=K;k++){
        for(let i=0;i<N;i++){
            for(let j=0;j<N;j++){
                for(let d=0;d<8;d++){
                    const newX = i+addX[d] 
                    const newY = j+addY[d] 
                    if(inBoard(N,newX,newY)){
                        //* 可以用两个数组交替，然后去掉第3维
                        dp[i][j][k] +=0.125 * dp[newX][newY][k-1]
                    }
                }
            }
        }
    }
    let ans = 0 
    for(let i=0;i<N;i++){
        for(let j=0;j<N;j++){
            ans+=dp[i][j][K]
        }
    }
    return ans
};